移除未排序链表的重复节点

发表于 | 分类于 |
字数统计: 644 字 | 阅读时长 ≈ 2 分钟

题目描述：编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例 1：
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]

示例 2：
输入：[1, 1, 1, 1, 2]
输出：[1, 2]

提示：

  1. 链表长度在[0, 20000]范围内。
  2. 链表元素在[0, 20000]范围内。

进阶：
如果不得使用临时缓冲区，该怎么解决？

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public ListNode removeDuplicateNodes(ListNode head) {

  }
}

方法一：哈希表

对给定的链表进行一次遍历，并用一个哈希集合（HashSet）来存储所有出现过的节点。由于在大部分语言中，对给定的链表元素直接进行「相等」比较，实际上是对两个链表元素的地址（而不是值）进行比较。因此，我们在哈希集合中存储链表元素的值，方便直接使用等号进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
  public ListNode removeDuplicateNodes(ListNode head) {
    Set<Integer> set = new HashSet<>();
    ListNode temp = head;
    while(temp != null && temp.next != null) {
      set.add(temp.val);
      if(set.contains(temp.next.val)) {
        temp.next = temp.next.next;
      }else {
        temp = temp.next;
      }
    }
    return head;
  }
}

复杂度分析：

  • 时间复杂度：O(N)，其中 N 是给定链表中节点的数目

  • 空间复杂度：O(N)。在最坏情况下，给定链表中每个节点都不相同，哈希表中需要存储所有的 N 个值

执行结果：通过

  • 执行用时：8 ms, 在所有 Java 提交中击败了32.95%的用户

  • 内存消耗：40.7 MB, 在所有 Java 提交中击败了74.14%的用户

方法二：两重循环

第一重循环枚举保留的节点本身，，第二重循环可以枚举待移除节点的前驱节点，方便我们对节点进行移除。这样一来，我们使用「时间换空间」的方法，就可以不使用临时缓冲区解决本题了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
  public ListNode removeDuplicateNodes(ListNode head) {
    if(head == null) return null;
    ListNode latter = head;
    while(latter != null) {
      ListNode pre = latter;
      while(pre.next != null) {
        if(pre.next.val == latter.val) {
          pre.next = pre.next.next;
        } else {
          pre = pre.next;
        }
      }
      latter = latter.next;
    }
    return head;
  }
}

复杂度分析：

  • 时间复杂度：O(N2)，其中 N 是给定链表中节点的数目
  • 空间复杂度：O(1)

执行结果：通过

  • 执行用时：394 ms, 在所有 Java 提交中击败了11.75%的用户

  • 内存消耗：40.3 MB, 在所有 Java 提交中击败了90.93%的用户